1564. Number theory

 

For the given positive integer n find the number of integers m, such that 1 ≤ m ≤ n, GCD(m, n) ≠ 1 and GCD(m, n) ≠ m. GCD  is an abbreviation for “greatest common divisor”.

 

Input. Each line contains one positive integer n (0 < n < 231).

 

Output. For each number n print the number of required integers m.

 

Sample input

Sample output

1

6

10

2147000000

0

1

3

1340599805

 

 

SOLUTION

number theory – Euler function

 

Algorithm analysis

From the number n, we must subtract the number of coprime numbers with n, that equals to the Euler function j(n) (if m and n are coprime, then GCD(m, n) = 1), and the number of its divisors (if m is a divisor of n, then GCD(m, n) = m). In this case, the number 1 will be simultaneously coprime with n and a divisor of n. Therefore, 1 should be added to the resulting difference.

If n =  is a factorization of n, it has d(n) = (k1 + 1) * (k2 + 1) * … * (kt + 1) divisors.

Thus, the number of required values of m for the given n equals to

n – j(n) – d(n) + 1

 

Example

Let n = 10. We have j(10) = 4 coprime numbers with 10: 1, 3, 7, 9.

Number 10 has d(10) = d(2 * 5) = 2 * 2 = 4 divisors: 1, 2, 5, 10.

The number of integers m, such that 1 ≤ m ≤ 10, GCD(m, 10) ≠ 1 and GCD(m, 10) ≠ m is

10 – j(10) – d(10) + 1 = 10 – 4 – 4 + 1 = 3

 

Algorithm realization

Function euler calculates the Euler function. At the same time, in the variable common, we count the number of divisors of the number n using the above formula. In the for loop, when we meet the divisor i of n, in the variable div we calculate the degree with which i is included in the number n. That is, div is the maximum degree for which n is divisible by idiv.

 

int euler(int n)

{

  int i, result = n, div;

  common = 1;

  for(i = 2; i <= sqrt(n); i++)

    if (n % i == 0)

    {

      div = 0;

      result -= result / i;

      while (n % i == 0) {n /= i; div++;}

      common *= div + 1;

    }

  if (n > 1) {result -= result / n; common *= 2;}

  return result;

}

 

The main part of the program. For each value of n calculate the result n – j(n) – common + 1, where common = (k1 + 1) * (k2 + 1) * … * (kt + 1), and print it.

 

while(scanf("%d",&n) == 1)

{

  res = n - euler(n) - common + 1;

  printf("%d\n",res);

}